// https://www.lintcode.com/problem/yang-hui-triangle/

public class Solution {
    /**
     * @param n: a Integer
     * @return: the first n-line Yang Hui's triangle
     */
    public List<List<Integer>> calcYangHuisTriangle(int n) {
        // write your code here
        List<List<Integer>> ret = new ArrayList<>();
        if (n == 0) {
            return ret;
        }
        ret.add(Arrays.asList(new Integer[]{1}));
        for (int i = 1; i < n; ++i) {
            List<Integer> level = new ArrayList<>();
            level.add(1);
            List<Integer> prev_level = ret.get(ret.size() - 1);
            for (int j = 0; j < (prev_level.size() - 1); ++j) {
                level.add(prev_level.get(j) + prev_level.get(j + 1));
            }
            level.add(1);
            ret.add(level);
        }
        return ret;
    }
}